{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# 529. Minesweeper\n",
    "\n",
    "Let's play the minesweeper game ([Wikipedia](https://en.wikipedia.org/wiki/Minesweeper_(video_game)), [online game](http://minesweeperonline.com/))!\n",
    "\n",
    "You are given a 2D char matrix representing the game board. **'M'** represents an **unrevealed** mine, **'E'** represents an **unrevealed** empty square, **'B'** represents a **revealed** blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, **digit** ('1' to '8') represents how many mines are adjacent to this **revealed** square, and finally **'X'** represents a **revealed** mine.\n",
    "\n",
    "Now given the next click position (row and column indices) among all the **unrevealed** squares ('M' or 'E'), return the board after revealing this position according to the following rules:\n",
    "    1. If a mine ('M') is revealed, then the game is over - change it to **'X'**.\n",
    "    2. If an empty square ('E') with **no adjacent mines** is revealed, then change it to revealed blank ('B') and all of its adjacent unrevealed squares should be revealed recursively.\n",
    "    3. If an empty square ('E') with **at least one adjacent mine** is revealed, then change it to a digit ('1' to '8') representing the number of adjacent mines.\n",
    "    4. Return the board when no more squares will be revealed.\n",
    "\n",
    "\n",
    "    Example 1:\n",
    "        Input:\n",
    "            [['E', 'E', 'E', 'E', 'E'],\n",
    "             ['E', 'E', 'M', 'E', 'E'],\n",
    "             ['E', 'E', 'E', 'E', 'E'],\n",
    "             ['E', 'E', 'E', 'E', 'E']]\n",
    "\n",
    "            Click : [3,0]\n",
    "\n",
    "        Output:\n",
    "            [['B', '1', 'E', '1', 'B'],\n",
    "             ['B', '1', 'M', '1', 'B'],\n",
    "             ['B', '1', '1', '1', 'B'],\n",
    "             ['B', 'B', 'B', 'B', 'B']]\n",
    "        Explanation:\n",
    "<div align=\"center\">\n",
    "    <img src=\"./images/minesweeper_example_1.png\" width=\"50%\">\n",
    "</div>\n",
    "\n",
    "    Example 2:\n",
    "        Input:\n",
    "            [['B', '1', 'E', '1', 'B'],\n",
    "             ['B', '1', 'M', '1', 'B'],\n",
    "             ['B', '1', '1', '1', 'B'],\n",
    "             ['B', 'B', 'B', 'B', 'B']]\n",
    "\n",
    "            Click : [1,2]\n",
    "\n",
    "        Output:\n",
    "            [['B', '1', 'E', '1', 'B'],\n",
    "             ['B', '1', 'X', '1', 'B'],\n",
    "             ['B', '1', '1', '1', 'B'],\n",
    "             ['B', 'B', 'B', 'B', 'B']]\n",
    "\n",
    "        Explanation:\n",
    "<div align=\"center\">\n",
    "    <img src=\"./images/minesweeper_example_2.png\" width=\"50%\">\n",
    "</div>\n",
    "\n",
    "Note:\n",
    "    1. The range of the input matrix's height and width is [1,50].\n",
    "    2. The click position will only be an unrevealed square ('M' or 'E'), which also means the input board contains at least one clickable square.\n",
    "    3. The input board won't be a stage when game is over (some mines have been revealed).\n",
    "    4. For simplicity, not mentioned rules should be ignored in this problem. For example, you **don't** need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:\n",
    "        direction = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]        \n",
    "        def dfs(x, y):\n",
    "            cnt = 0\n",
    "            for dx, dy in direction:\n",
    "                tx = x + dx\n",
    "                ty = y + dy\n",
    "                if tx < 0 or tx >= len(board) or ty < 0 or ty >= len(board[0]):\n",
    "                    continue\n",
    "                # 不用判断 M，因为如果有 M 的话游戏已经结束了\n",
    "                cnt += board[tx][ty] == 'M'\n",
    "            \n",
    "            if cnt > 0:\n",
    "                # 规则 3\n",
    "                board[x][y] = str(cnt)\n",
    "            else:\n",
    "                # 规则 2\n",
    "                board[x][y] = 'B'\n",
    "                for dx, dy in direction:\n",
    "                    tx = x + dx\n",
    "                    ty = y + dy\n",
    "                    # 这里不需要在存在 B 的时候继续扩展，因为 B 之前被点击的时候已经被扩展过了\n",
    "                    if tx < 0 or tx >= len(board) or ty < 0 or ty >= len(board[0]) or board[tx][ty] != 'E':\n",
    "                        continue\n",
    "                    dfs(tx, ty)\n",
    "    \n",
    "        if board[click[0]][click[1]] == 'M':            \n",
    "            # 规则 1\n",
    "            board[click[0]][click[1]] = 'X'\n",
    "        else:\n",
    "            dfs(click[0], click[1])\n",
    "        \n",
    "        return board\n",
    "\n",
    "\n",
    "S = Solution()"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['B', '1', 'E', '1', 'B'], ['B', '1', 'M', '1', 'B'], ['B', '1', '1', '1', 'B'], ['B', 'B', 'B', 'B', 'B']]\n"
     ]
    }
   ],
   "source": [
    "board = [['E', 'E', 'E', 'E', 'E'],\n",
    " ['E', 'E', 'M', 'E', 'E'],\n",
    " ['E', 'E', 'E', 'E', 'E'],\n",
    " ['E', 'E', 'E', 'E', 'E']]\n",
    "\n",
    "Click = [3,0]\n",
    "\n",
    "S.updateBoard(board, Click)\n",
    "\n",
    "print(board)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "3.7.2-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}